//
// Created by xili on 2024/8/8 20:56.
// Go big or go home.
//

using namespace std;

struct ListNode {
    int val;
    ListNode *next;

    ListNode() : val(0), next(nullptr) {}

    ListNode(int x) : val(x), next(nullptr) {}

    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    ListNode *findmid(ListNode *l, ListNode *r) {
        ListNode *s = l;
        ListNode *f = l;
        while (f != r && f->next != r) {
            s = s->next;
            f = f->next->next;
        }
        return s;
    }

    TreeNode *bulid(ListNode *l, ListNode *r) {
        if (l == r) {
            return nullptr;
        }
        ListNode *m = findmid(l, r);
        TreeNode *root = new TreeNode(m->val);
        root->left = bulid(l, m);
        root->right = bulid(m->next, r);
        return root;
    }

    TreeNode *sortedListToBST(ListNode *head) {
        return bulid(head, nullptr);
    }
};